package site.zhouinfo.zhihuproblem;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Random;
import java.util.concurrent.CountDownLatch;

/**
 * 问题:
 * 600个人站一排，每次随机杀掉一个奇数位的人，几号最安全？
 * 最安全参考两种定义方式:
 * <p>
 * 1.杀死需要的次数的期望值最大。
 * 2.成为最后一个被杀死的概率最大。
 *
 * @author zhou
 * @create 2017-02-17 11:40
 * @email zhouinfo@qq.com
 */
public class KillNumber {

    //修改这里
    public static final int NUMBER = 600;              //人数
    public static final int CYCLE_INDEX = 10000 * 100;       //循环次数
    public static final int CPU_CORE = 8;       //循环次数

    public static Random random = new Random();        //随机数
    public static int[] surviveNumber = new int[NUMBER];     //CYCLE_INDEX次循环 幸存的次数
    public static int[] expectedMean = new int[NUMBER];  //CYCLE_INDEX次循环 期望存活回合平均值
    public static ArrayList<Integer> list = new ArrayList<Integer>();   //相当于链表数据 方便删除
    //格式化数据
    public static DecimalFormat dfNumber = new DecimalFormat("000");
    public static DecimalFormat dfSurvive = new DecimalFormat("0000");
    public static DecimalFormat dfSurviveHz = new DecimalFormat("0.000000");
    public static DecimalFormat dfExpected = new DecimalFormat("0.00000000");

    public static long time = 0;

    public static void main(String[] args) {
        for (int i = 0; i < NUMBER; i++) {
            surviveNumber[i] = 0;
            list.add(i + 1);
        }
        KillNumberOne();

        //KillNumberTwo();
    }

    /**
     * 单线程处理
     */
    public static void KillNumberOne() {
        System.out.println("单线程开始");
        time = System.currentTimeMillis();
        for (int i = 0; i < CYCLE_INDEX; i++) {
            surviveNumber[cycleProcess(list) - 1]++;
        }
        time = System.currentTimeMillis() - time;
        //print();
        System.out.println("单线程结束" + time + " ms");
    }

    /**
     * 多线程处理
     */
    public static void KillNumberTwo() {
        System.out.println("多线程开始");
        CountDownLatch latch = new CountDownLatch(CPU_CORE);
        time = System.currentTimeMillis();
        for (int i = 0; i < CPU_CORE; i++) {
            Thread thread = new Thread(new KillNumberThread(latch));
            thread.start();
        }
        try {
            latch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        time = System.currentTimeMillis() - time;
        print();
        System.out.println("8个多线程结束" + time + " ms");
    }


    /**
     * 模拟一次循环的过程
     *
     * @param list 编号数据列表
     * @return 幸存编号
     */
    public static Integer cycleProcess(Collection<Integer> list) {
        ArrayList<Integer> resultList = new ArrayList<Integer>(list);
        for (int i = 0; i < NUMBER - 1; i++) {
            int kill = getRandomKillNumber(NUMBER - i);
            int n = resultList.remove(kill - 1);//移除的编号n
            expectedMean[n - 1] = expectedMean[n - 1] + i + 1;//统计每次循环的次序
        }
        return resultList.get(0);
    }

    /**
     * 获取随机奇数
     * (size & 1) == 1      奇数
     * (randomInt & 1) == 0 偶数
     *
     * @param size 剩余的编号数量 ∈[0,resultList.size)
     * @return 随机奇数 randomInt=2k-1, k∈[1,size]
     */
    public static int getRandomKillNumber(int size) {
        int randomInt = random.nextInt((size & 1) == 1 ? size + 1 : size) + 1;    //randomInt=randomInt+1, randomInt∈[1,size]
        return (randomInt & 1) == 0 ? randomInt - 1 : randomInt;                  // kill = 2k-1, k∈[1,size]
    }

    /**
     * 打印
     */
    public static void print() {
        System.out.println("编号" + "\t" +
                "\t" + "幸存次数" + "\t\t" + "幸存频率" + "\t\t\t" + "幸存回合期望值");
        for (int i = 0; i < NUMBER; i++) {
            System.out.println(dfNumber.format(i + 1) + "\t\t"
                    + dfSurvive.format(surviveNumber[i]) + "\t\t"
                    + dfSurviveHz.format(surviveNumber[i] / (CYCLE_INDEX * 1.0)) + "\t\t"
                    + dfExpected.format(expectedMean[i] / (CYCLE_INDEX * NUMBER + 0.0)));
        }
        System.out.println("编号总数: \t" + NUMBER + "\t\t循环次数: \t" + CYCLE_INDEX);
    }

}
